package com.cat.chapter049;

import com.sun.security.auth.UnixNumericGroupPrincipal;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author cat
 * @description https://leetcode.cn/problems/subarrays-with-k-different-integers/
 * @create 2025/7/19 15:57
 * @since JDK17
 */

public class Solution06 {
    static int[] h = new int[20010];
    public int subarraysWithKDistinct(int[] nums, int k) {
        Arrays.fill(h, 0, nums.length, 0);  // 清理数组
        return f(nums, k) - f(nums, k - 1);
    }

    public int f(int[] nums, int k) {
        int ans = 0, collect = 0, n = nums.length;
        for (int l = 0, r = 0; r < n; r++) {
            collect += h[nums[r]]++ == 0 ? 1 : 0;   // 新增一种数字
            while (collect > k) {   // 超过了k个
                collect -= h[nums[l++]]-- == 1 ? 1 : 0;
            }
            ans += r - l + 1;   // 收集答案
        }
        return ans;
    }
}
